Methods for handling deadlock
There are three ways to handle deadlock
- Deadlock Prevention: The OS accepts all the sent requests. The idea is to not to send a request that might lead to a deadlock condition.
- Deadlock Avoidance: The OS very carefully accepts requests and checks whether if any request can cause deadlock and if the process leads to deadlock, the process is avoided.
- Deadlock Detection and Recovery: Let deadlock occur, then do preemption to handle it once occurred.
- Ignore the problem altogether: If the deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.
Deadlock Characteristics
As discussed in the
previous post, deadlock has following characteristics.
- Mutual Exclusion
- Hold and Wait
- No preemption
- Circular wait
Deadlock Prevention
We can prevent Deadlock by eliminating any of the above four conditions.
- Eliminate Mutual Exclusion: It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tap drive and printer, are inherently non-shareable. It can be avoided to some extent using Spooling.
- Eliminate Hold and wait:
- Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the start of its execution printer will remain blocked till it has completed its execution.
- The process will make a new request for resources after releasing the current set of resources. This solution may lead to starvation.

- Eliminate No Preemption: Preempt resources from the process when resources required by other high priority processes.
- Eliminate Circular Wait: Each resource will be assigned with a numerical number. A process can request the resources only in increasing order of numbering.
For Example, if the P1 process is allocated R1, P2 has R2 and P3 has R3, then P3 cannot request R1 which is less than R3.

Deadlock Avoidance
Deadlock avoidance can be done with Banker's Algorithm.
If a system does not employ either a deadlock prevention or
deadlock avoidance algorithm then a deadlock situation may occur. In this case-
- Apply an algorithm to examine state of system to determine whether deadlock has has occurred or not.
- Apply an algorithm to recover from the deadlock. For more refer- Deadlock Recovery
Deadlock Detection Algorithm/Bankers Algorithm:
It is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
The algorithm employs several time varying data structures:
- Available- A vector of length m indicates the number of available resources of each type.
- Allocation- An n*m matrix defines the number of resources of each type currently allocated to a process. Column represents resource and resource represent process.
- Request- An n*m matrix indicates the current request of each process. If request[i][j] equals k then process Pi is requesting k more instances of resource type Rj.
We treat rows in the matrices Allocation and Request as vectors, we refer them as Allocation
i and Request
i.
Steps of Algorithm:
- Let Work and Finish be vectors of length m and n respectively. Initialize Work= Available. For i=0, 1, ...., n-1, if Allocationi = 0, then Finish[i] = true; otherwise, Finish[i]= false.
- Find an index i such that both
a) Finish[i] == false
b) Requesti <= Work
If no such i exists go to step 4.
- Work= Work+ Allocationi
Finish[i]= true
Go to Step 2.
- If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process Pi is deadlocked.
Example 1:
- In this, Work = [0, 0, 0] &
Finish = [false, false, false, false, false]
- i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
- Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].
- i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
- Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].
- i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
- Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].
- i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3].
- Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].
- i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].
- Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].
- Since Finish is a vector of all true it means there is no deadlock in this example.
Example 2:
Considering a system with five processes P0 through P4 and three resources of type A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:
Question1. What will be the content of the Need matrix?
Need [i, j] = Max [i, j] – Allocation [i, j]
So, the content of Need Matrix is:
Question2. Is the system in a safe state? If Yes, then what is the safe sequence?
Applying the Safety algorithm on the given system,
Question3. What will happen if process P1 requests one additional instance of resource type A and two instances of resource type C?
We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the above data structures.
Hence the new system state is safe, so we can immediately grant the request for process
P1 .